00100	WHAT IS A PATTERN?
00200	
00300	
00400		In many areas of programming and especially in artificial
00500	intelligence, it is effective to create and use patterns.  The use
00600	involves recognizing the pattern in a situation and taking
00700	an appropriate action.  More generally, the acton taken may depend
00800	on a set of patterns and other information as well.
00900	
01000		The most well developed forms of pattern and pattern
01100	recognition occur in formal syntax of languages where the
01200	languages are strings of symbols.  I want to define patterns
01300	abstractly quite separately from language but hopefully in a way
01400	that is applicable to language and in a way that will enable
01500	some of the properties of linguistic patterns that have been
01600	studied to carry over to \F1abstract patterns\F0.
01700	
01800		When I have tried to give a flly general definition of
01900	pattern, the ideas have gotten quite complex and no \F1most general\F0
02000	idea has come out.  Therefore, I will try to sneak up on it
02100	and start with the simplest kinds of patterns.
02200	
02300	
02400	Type I patterns
02500	
02600		A type I pattern is scified by giving a collection
02700	of predicates and a quantifier free expression in these
02800	predicate symbols.  An instance of the pattern is a pairing of
02900	entities with the free individual variables such that when
03000	the variables are assigned the corresponding entities, the
03100	expression is true.
03200	
03300		The notion of pin in chess can be given as
03400	an example of a type I pattern provided i? is described in
03500	terms of the following predicates:
03600	
03700		1. iswhite(piece) asserts that \F1piece\F0 is white.
03800	
03900		2. sees(piece1,piece2,direction,board) asserts that
04000	if one moves from \F1piece1\F0 in the direction \F1direction\F0
04100	on the board situation \F1board\F0, one encounters \F1pieceF0
04200	before encountering a non-blank square or the edge of the
04300	board.
04400	
04500		2. moves(piece,direction) asserts that \F1piece\F0
04600	moves an arbitrary distance, (it therefore must be a
04700	queen, rook, or bishop) in \F1direction\F0.
04800	
04900		3. better(piece1,piece2) asserts that \F1piece1\F0
05000	has a higher value than \F1piece2\F0.
05100	
05200		4. defended(piece,board) asserts that \F1piece\F0 is
05300	defended in the position \F1board\F0.
05400	
05500		Pins are then described by a formula involving five
05600	free variables, namely \F1piece1\F0 - the pinning piece,
05700	\F1piece2\F0 - the pinned piece, \F1piece3\F0 - the piece
05800	against which \F1piece2\F0 is pinned, \F1direction\F0 -
05900	the direction from \F1piece1\F0 to \F1piece2\F0, and 
06000	\F1board\F0 - theosition in which all this occurs.  The formula
06100	is
06200		\F1iswhite(piece1) ≡ iswhite(piece3) ∧
06300		iswhite(piece1) ≡ ¬iswhite(piece2) ∧
06400		sees(piece1,piece2,direction,board) ∧
06500		sees(piece2,piece3,direction,board) ∧
06600		moves(piece1,direction) ∧
06700		[¬defended(piece3,board) ∨ better(piece3,piece1)].
06800	
06900		This simple example suggests the following remarks:
07000	
07100		1. The simplest linguistic patterns are of type I.
07200	These give a special role to the relation
07300	
07400		ispredecessor(string1,string2,string3)
07500	
07600	which asserts that \F1string1\F0 immediately precedes
07700	\F1string2\F0 in their occurence as substrings of \F1string3\F0.
07800	
07900	Thus strings consisting of noun phrases followed by verb phrases
08000	which give one form of sentence in some simple grammars are
08100	examples of the pattern
08200	
08300		ispredecessor(string1,string2,string3) ∧
08400		nounphrase(string1) ∧
08500		verbphrase(string2).
08600	
08700		2. Since a substantial part of the generalization we are
08800	looking for consists merely in not giving a special roll to the
08900	relation \F1ispredecessor\F0, it is likely that some of the
09000	interesting properties of string patterns carry over to the
09100	general case.
09200	
09300		3. Given the small number of pieces in/a chess position,
09400	it is clearly feasible to find pins in a position given
09500	programs for calculating the predicates involved.  This involves
09600	specifying one of the elements of the pattern, namely \F1board\F0
09700	which thereby plays a special role and scanning the others.
09800	An ad hoc pin recognizer is clearly easy to write, and it
09900	is even easy to write a general pattern recognizer for patterns
10000	involving a single board variable, several piece variables, and
10100	several direction variables.
10200	However, a recognizer that had to scan all possible positions
10300	is infeasible and not wanted for chess play anyway.  Moreover,
10400	the different roles played by pieces and directions (e.g. it
10500	if we scan the potential pinning pieces and the directions
10600	leading from them first, we need only look for potential
10700	pinned pieces in the given direction), makes it unlikely that
10800	the techniques of grammatical pattern recognition have much
10900	carryover to the general case.
11000	
11100		4. One is tempted to use existing patterns in
11200	dfining new patterns, and in order to do this, we need to
11300	allow binding some variables with existential quantifiers.
11400	Thus we obvusly want to define
11500	
11600		pinned(piece,board) ≡ ∃ piece1 piece3 direction.
11700			pins(piece1,piece,piece3,direction,board),
11800	
11900	and the predicate \F1defended\F0 used in the definition of
12000	\F1pins\F0 obviously wants to be defined in terms of a pattern.
12100	
12200		In the study of grammatical patterns, the highly recursive
12300	cases are emphasized, because they are necessary for any kind
12400	of generality, because Chomsky fascinated the linguists
12500	with the competence-performance distinction, and because
12600	they are mathematically the most interesting.  Nevertheless,
12700	non-recursive patterns occur in many practical cases and probably usually
12800	admit simpler methods of recognition and use.
13000	Therefore we shall take type I patterns to be non-recursive,
13100	and reserve recursion for a later type.
13200	
13300		5. In one respect, type I patterns go beyond context free
13400	phrase structure grammars in the string case.  Namely, the
13500	same variabl∨ occurs in arbitrary places in the defining
13600	expression, and this allows the imposition of requirements
13700	of agreement from the beginning.  I doubt that the requirement
13800	that all occurences of variables be of different variables
13900	leads to an interesting class of patterns.  Moreover, it
14000	doesn't give the context free patterns in the grammar case
14100	unless we distinguish the \F1ispredecessor\F0 function,
14200	because a varible has to occur in the \Fispredecessor\F0
14300	relation and also in the other predicates.  This simply
14400	confirms my prejudice against context freedom.
14500	
14600		6. In writing the \F1pin\F0 pattern, it was
14700	an inconvenience not to be able to use the function
14800	\F1color(piece)\F0, but we got around it with the
14900	predicate \F1iswhite\F0 at the cost of awkwardness.
15000	It would seem that any pattern that can be written
15100	with functions can also be written using only the
15200	corresponding predicates provided we use existential
15300	quantifiers to get rid of unwanted variables that have to
15400	be introduced.  Thus the relation
15500	
15600		y = f(g(h(x)))
15700	
15800	which might occur in some pattern would have to be
15900	replaced by
16000	
16100		F(y,u) ∧ G(u,v) ∧ H(v,x)
16200	
16300	where f and F are related by
16400	
16500		∀ x y.(y = f(x) ≡ F(y,x)).
16600	
16700	Thus we would get a pattern with more variables, and the
16800	extras can be eliminated with existential quantifiers.
16900	Suppose we call the patterns we get allowing function
17000	symbols type I-a.  It is an open question whether we should
17100	do this or whether we should admit the function symbols
17200	directly into type I.
17300	
17400		6. We shall not try to define more types of patterns
17500	in this draft.  However, noote the following directions of
17600	generalization:
17700	
17800			a. The computation of the predicate expression
17900	could involve more complicated calculations such as recursion.
18000	Thus a pin is not a type I pattern if we can't use
18100	\F1sees(piece1,piece2,direction,board)\F0, but have to build
18200	it from the relation \F1adjacent(square1,square2,direction)\F0.
18300	
18400			b. Variable numbers of entities may appear in
18500	patterns.
18600	
18700			c. The conditions for one pattern may require
18800	the non-existence of other patterns.
18900	
19000		7. The example of pinning shows that patterns may be
19100	used in much more varied ways than in linguistics whether of
19200	natural or computer languages.  Some typology of the ways
19300	in which patterns are used after being recognized is probably
19400	worthwhile.